/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 *
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *
 * 你的算法时间复杂度必须是 O(log n) 级别。
 *
 * 如果数组中不存在目标值，返回 [-1, -1]。
 *
 * 示例 1:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: [3,4]
 *
 * 示例 2:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: [-1,-1]
 *
 * 难点：
 *       确定边界，即要找到的目标数
 *
 *  解题：二分查找
 *      下边界：如果这个数等于target并且它的前一个数小于target，或者它是最左边的数，那么它就是下边界
 *      上边界：如果这个数等于target并且它的后一个数大于target，或者它是最右边的数，那么它就是上边界
 *
 *
 */


public class Solution_034 {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int result[] = new int[2];
        result[0] = searchLowerBound(nums,target,0, n-1);
        result[1] = searchUpperBound(nums,target,0, n-1);
        return result;
    }

    int searchLowerBound(int[] nums,int target,int low,int high) {
        //是否满足查找条件，即low <= hign
        if(low > high) {
            return -1;
        }
        //计算middle
        int middle = low + (high - low) / 2;

        //判断是否满足下边界条件
        if (nums[middle] == target && (middle == 0 || nums[middle-1] < target)) {
            return middle;
        }

        //继续二分查找
        //TODO 理解这里为什么要小于等于
        /**
         * 左边有与之相同的数时，继续递归查找左半边
         */
        if (target <= nums[middle]) {
            //target在左半边
            return searchLowerBound(nums,target,low,middle-1);
        }else {
            //target在右半边
            return searchLowerBound(nums,target,middle+1,high);
        }
    }

    int searchUpperBound(int[] nums,int target,int low,int high) {
        //是否满足查找条件，即low <= hign
        if(low > high) {
            return -1;
        }
        //计算middle
        int middle = low + (high - low) / 2;

        //判断是否满足下边界条件
        if (nums[middle] == target && (middle == nums.length - 1 || nums[middle+1] > target)) {
            return middle;
        }

        //继续二分查找
        //TODO 搞清楚这里为什么不是小于等于
        /**
         * 因为条件是 target >= nums[middle]时才继续递归查找右半边
         * 变换一下就是target < nums[middle]时递归查找左半边
         */
        if (target < nums[middle]) {
            //target在左半边
            return searchUpperBound(nums,target,low,middle-1);
        }else {
            //target在右半边
            return searchUpperBound(nums,target,middle+1,high);
        }
    }
}
